Luogu-1282-多米诺骨牌

2019-10-21 ACM 阅读量

多米诺骨牌有上下2个方块组成，每个方块中有1~6个点。现有排成行的上方块中点数之和记为S1，下方块中点数之和记为S2，它们的差为|S1-S2|。例如在图8-1中，S1=6+1+1+1=9，S2=1+5+3+2=11，|S1-S2|=2。每个多米诺骨牌可以旋转180°，使得上下两个方块互换位置。编程用最少的旋转次数使多米诺骨牌上下2行点数之差达到最小。

对于图中的例子，只要将最后一个多米诺骨牌旋转180°，可使上下2行点数之差为0。

题目链接

Luogu-1282-多米诺骨牌

输入输出格式

输入格式

输入文件的第一行是一个正整数 $n(1 \leq n \leq 1000)$ ，表示多米诺骨牌数。接下来的n行表示 $n$ 个多米诺骨牌的点数。每行有两个用空格隔开的正整数，表示多米诺骨牌上下方块中的点数 $a$ 和 $b$，且 $1\leq a，b \leq 6$ 。

输出格式

输出一行，为世界末日的日期，每个数字之间用一个空格隔开。

输入输出样例

输入样例1：

输出样例1：

题解

很显然是个 dp 题目，显然蓝题 dp 我不会写，自己瞎定义了一个 $dp[i][j]$ ，发现没法进行状态转移，看了题解说我定义的方程太麻烦很难写？？？？喵喵喵？？？然后看了题解的 $dp$ 的定义方法，写了下去。

一开始我定义的 $dp[i][j]$ 是前 $i$ 个牌，翻转 $j$ 次的上下差值。我不会推状态转移方程，后期刷多了再推把。

题解的定义为 $dp[i][j]$ 代表前 $i$ 个牌组成和为 $j$ 的旋转次数。对于这种定义，我们可以暴力枚举，前 $i$ 能组成的所有和，即

$dp[i][j] = min(dp[i][j],dp[i-1][j - a[i]]) // 不翻转$
$dp[i][j] = min(dp[i][j],dp[i-1][j - b[i]] + 1) // 翻转$

对于 $j$ 而言，前 $i$ 个骨牌所能组成的最大总和为 $6 * n$ ，所以时间复杂度为 $O(6*n^2)$

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 3e3 + 5;
const int MOD = 1e9+7;
const int INF = 0x3f3f3f3f;
int dp[1005][6005];
int a[MAXN],b[MAXN];
int main() {
    ios::sync_with_stdio(false);
    int n,sum = 0;
    cin >> n;
    for(int i = 1;i <= n;i++){
        cin >> a[i] >> b[i];
        sum += a[i] + b[i];
    }
    memset(dp,INF,sizeof(dp));//最初所有能组成的点数之和的翻转次数都是INF
    dp[1][a[1]] = 0;dp[1][b[1]] = 1; //第一块骨牌的上为0，下为1
    
    for(int i = 2;i <= n;i++){
        for(int j = 1;j <= 6*n;j++){
            if(j >= a[i])
                dp[i][j] = min(dp[i][j],dp[i-1][j - a[i]]);
            if(j >= b[i])
                dp[i][j] = min(dp[i][j],dp[i-1][j - b[i]] + 1);
        }
    }

    int cut = INF,cnt = INF;
    for(int i = 1;i <= sum;i++){
        if(dp[n][i] != INF){ //如果这n个牌能到达和为i
            if(cut > abs(i - (sum - i))){
                cut = abs(i - (sum - i));
                cnt = dp[n][i];
            } else if(cut == abs(i - (sum - i))){
                cnt = min(cnt,dp[n][i]);
            }
        }
    }
    cout << cnt << endl;
    return 0;
}